#include <iostream>
#include <vector>
#include <unordered_map>
#include <numeric>
using namespace std;

class Solution
{
public:
    int minSizeSubarray(vector<int> &nums, int target)
    {
        unordered_map<int, int> mp;
        vector<unsigned int> prefix(nums.size(), 0);
        prefix[0] = nums[0];
        mp[prefix[0]] = 0;
        for (int i = 1; i < nums.size(); i++)
        {
            prefix[i] = prefix[i - 1] + nums[i];
            mp[prefix[i]] = i;
        }
        mp[0] = -1;
        int minLength = INT_MAX;
        int k = target / prefix[prefix.size() - 1];
        target = target % prefix[prefix.size() - 1];
        int subfix = 0;
        for (int i = nums.size() - 1; i >= 0; i--)
        {
            subfix += nums[i];
            int t = target - subfix;
            if (t >= 0 && mp.find(t) != mp.end())
            {
                int l = mp[t] + 1 + (k + 1) * nums.size() - i;
                minLength = min(minLength, l);
            }
            t = prefix[i] - target;
            if (t >= 0 && mp.find(t) != mp.end())
            {
                int l = i - mp[t] + k * nums.size();
                minLength = min(minLength, l);
            }
        }
        return minLength == INT_MAX ? -1 : minLength;
    }
};

int main()
{
    cout << "Code2875" << endl;
    Solution s;
    // vector<int> nums = {2, 1, 5, 7, 7, 1, 6, 3};
    vector<int> nums = {1, 2, 3};
    cout << s.minSizeSubarray(nums, 8) << endl;
    return 0;
}